/**
 * https://leetcode.cn/submissions/detail/570052302/
 * 337. 打家劫舍 III
 * Medium, 黄伟杰 2024.10.04
 * 树形DP
 */

#include <bits/stdc++.h>
using namespace std;

class Solution
{
    pair<int, int> dfs(TreeNode *node)
    {
        if (node == nullptr)
            return {0, 0};
        auto [rob_l, rob_not_l] = dfs(node->left);                   // 左子树
        auto [rob_r, rob_not_r] = dfs(node->right);                  // 右子树
        int rob = node->val + rob_not_l + rob_not_r;                 // 这个节点偷
        int rob_not = max(rob_l, rob_not_l) + max(rob_r, rob_not_r); // 这个节点不偷
        return {rob, rob_not};
    }

public:
    int rob(TreeNode *root)
    {
        auto [root_rob, root_not_rob] = dfs(root);
        return max(root_rob, root_not_rob);
    }